<?php


$values = array(1,5,9,15,18,22);

heapSort($values);

function heapSort(&$a) {
	$heapSize = count($a);
	buildHeap($a, $heapSize);
	while ($heapSize--) {
		// needed to maintain the previous max element at top
		$temp = $a[$heapSize];
		$a[$heapSize] = $a[0];
		$a[0] = $temp;
		buildHeap($a, $heapSize);
	}
}

function buildHeap(&$a, &$heapSize) {
	$length = floor($heapSize / 2);
	$i = $length;
	while ($i >= 0) {
		heapify($a, $i, $heapSize);
		$i--;
	}
}

function heapify(&$a, &$i, &$heapSize) {
	$left = $i*2 + 1;
	$right = $i*2 + 2;
	
	if ($left < $heapSize && $a[$i] < $a[$left]) {
		$largest = $left;
	} else {
		$largest = $i;
	}
	
	if ($right < $heapSize && $a[$largest] < $a[$right]) {
		$largest = $right;
	}
	
	if ($largest != $i) {
		$temp = $a[$i];
		$a[$i] = $a[$largest];
		$a[$largest] = $temp;
		
		heapify($a, $largest, $heapSize);
	}
}



